package com.ai.zuochengyun.phase01.class06;

import java.util.*;

/**
 * 最短路径
 */
public class Code08_Dijkstra {

    public static Map<Node, Integer> dijkstra1(Node from) {
        Map<Node, Integer> distanceMap = new HashMap<>();
        // 自己到自己的距离是0
        distanceMap.put(from, 0);
        Set<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        while (minNode != null) {
            int distance = distanceMap.get(minNode);
            // 当前节点接下来要经过的所有的边
            for (Edge edge : minNode.edges) {
                Node toNode = edge.to;
                if (!distanceMap.containsKey(toNode)) {
                    // 自己到自己的距离 加上 记下来要经过的边的权重
                    distanceMap.put(toNode, distance + edge.weight);
                } else {
                    // 当前边的权重和之前的值取较小的记录，作为下次比较的基准
                    distanceMap.put(toNode, Math.min(distanceMap.get(toNode), distance + edge.weight));
                }
            }
            // 所有的边都计算过后，找到了最小的距离，标记成已经计算好了，下次不再计算该节点
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);
        }
        return distanceMap;
    }

    /**
     * 使用加强堆的优化版本
     * @param from
     * @return
     */
    public static Map<Node, Integer> dijkstra2(Node from, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        return null;
    }

    private static Node getMinDistanceAndUnselectedNode(Map<Node, Integer> distanceMap, Set<Node> selectedNodes) {
        Node node = null;
        int distance = Integer.MAX_VALUE;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            if (entry.getValue() < distance && !selectedNodes.contains(entry.getKey())) {
                distance = entry.getValue();
                node = entry.getKey();
            }
        }
        return node;
    }
}
